package 算法.力扣;

/**
 * @author: 谢君臣
 * @create: 2020-09-09 21:59
 * @founction: 给定一个直方图(也称柱状图)，
 *      假设有人从上面源源不断地倒水，
 *      最后直方图能存多少水量?直方图的宽度为 1。
 */
public class Marcos {


    public static void main(String[] args) {

        int [] num = new int[]{4,2,3};
        trap(num);
        System.out.println(sum);
    }
    private static int sum;
    public static int trap(int[] height) {
        sum = 0;
        if (height.length<3){
            return 0;
        }else {
            int max_index = Max_index(height,0,height.length);
            left(height,0,max_index);
            right(height,max_index,height.length-1);
            return sum;
        }
    }
    private static void right(int[] height, int h, int e) {
        while (e-h>=2){
            // 循环
            int max_index = Max_index(height,h+1,e+1);
            Calcuate_R(height,h+1,max_index);
            // 计算容量
            h = max_index;
        }
    }

    private static void left(int[] height, int h, int e) {
        while (e-h>=2){
            // 循环
            int max_index = Max_index(height,0,e);
            Calcuate_L(height,max_index,e);
            // 计算容量
            e = max_index;
        }
    }

    static int Max_index(int[] height, int h , int e){
       int max_num = 0,index = 0;
       for (int i = h; i < e; i++) {
           if (height[i]>=max_num) {
               max_num = height[i];
               index = i;
           }
       }
       return index;
   }
   static void Calcuate_L(int[] height, int h , int e){
        for (int i =h;i<e;i++){
            sum+=height[h]-height[i];
        }
   }
    static void Calcuate_R(int[] height, int h , int e){
        for (int i =h;i<=e;i++){
            sum+=height[e]-height[i];
        }
    }
}
